package P2分治回溯;
//汉诺塔问题
/*
大问题化为小问题的过程
把移动n个盘子的问题 化解为 第n个盘子 与 前n-1个盘子 两个部分 进行移动
前n-1个盘子 也可以继续划分为 第n-1个盘子 与 前n-2个盘子 两个部分 以此类推
直到只有一个盘子为止

当前第n个盘子的移动，与前n-1个盘子移动的规律
当前的 过渡柱子 是 前n-1个盘子移动的 终点！
*/
public class Hanoi {
    public static void main(String[] args) {
        String X = "X";
        String Y = "Y";
        String Z = "Z";
        hanoi(3, X, Y, Z); //O(2^n)
    }

    private static void hanoi(int level, String begin, String mid, String end) {
        if (level == 1) {
            System.out.println(begin + "->" + end);
        } else {
            //核心 当前层的过渡是下一层的终点！！！
            //前level-1个盘子 从begin到mid
            hanoi(level - 1, begin, end, mid);
            //第level个盘子
            System.out.println(begin + "->" + end);
            //前level-1个盘子 从mid到end
            hanoi(level - 1, mid, begin, end);
        }
    }
}
